#include <iostream>
using namespace std;
int main()
{
    int w[1005], v[1005];
    int f[1005];
    int m, n;
    while (cin >> m >> n)
    {
        if (m == -1 && n == -1)
            return 0;
        memset(f, 0, sizeof(f));
        memset(w, 0, sizeof(w));
        memset(v, 0, sizeof(v));
        f[0] = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> w[i] >> v[i];
        }
        for (int i = 0; i <= n; i++)
        {
            for (int j = m; j >= v[i]; j--)
            {
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
        }
        cout << f[m] << endl;
    }
}
